skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Neeman, Joe"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; (, Random Structures & Algorithms)
    Bohman, T (Ed.)
    Abstract We prove moderate deviations bounds for the lower tail of the number of odd cycles in a random graph. We show that the probability of decreasing triangle density by , is whenever . These complement results of Goldschmidt, Griffiths, and Scott, who showed that for , the probability is . That is, deviations of order smaller than behave like small deviations, and deviations of order larger than behave like large deviations. We conjecture that a sharp change between the two regimes occurs for deviations of size , which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. We give analogous results for the ‐cycle density, for all odd . Our results can be interpreted as finite size effects in phase transitions in constrained random graphs. 
    more » « less
    Full Text Available 
  2. ; ; (, Probability Theory and Related Fields)
    Full Text Available 
  3. ; ; (, Proceedings of the Annual ACM Symposium on Theory of Computing)
    Full Text Available 
  4. ; ; (, Annual Symposium on Foundations of Computer Science)
    Full Text Available 
  5. ; ; (, Proceedings of Machine Learning Research)
    Accepted Manuscript Full Text Available
  6. ; ; ; ; (, Random Structures & Algorithms)
    Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from(and hence is likely to have a clique of size roughly), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesnδprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than. 
    more » « less